package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/4sum/description/">18. 四数之和</a>
 */
class Solution18 {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        val rst = ArrayList<List<Int>>()
        if (nums.size < 4) {
            return rst
        }
        nums.sort()

        var i = 0
        while (i < nums.size - 3) {
            if (checkOut(nums, target, i, i + 1)) {
                break
            }
            var j = i + 1
            while (j < nums.size - 2) {
                if (checkOut(nums, target, i, j)) {
                    break
                }
                findRst(nums, target.toLong(), nums[i], nums[j], rst, j)
                j = findNext(nums, j, 2)
            }
            i = findNext(nums, i, 3)
        }

        return rst
    }

    private fun findRst(nums: IntArray, target: Long, nowA: Int, nowB: Int, result: ArrayList<List<Int>>, offset: Int) {
        var l = offset + 1
        var r = nums.size - 1
        while (l < r) {
            val sum = nums[l].toLong() + nums[r] + nowA + nowB
            if (sum > target) {
                r--
            } else if (sum < target) {
                l++
            } else {
                result.add(arrayOf(nowA, nowB, nums[l], nums[r]).toList())
                while (l < r) {
                    l++
                    if (nums[l - 1] != nums[l]) {
                        break
                    }
                }
                while (l < r) {
                    r--
                    if (nums[r + 1] != nums[r]) {
                        break
                    }
                }
            }
        }
    }

    private fun findNext(nums: IntArray, now: Int, limit: Int): Int {
        var n = now
        while (n < nums.size - limit) {
            n++
            if (nums[n - 1] != nums[n]) {
                break
            }
        }
        return n
    }

    private fun checkOut(nums: IntArray, target: Int, a: Int, b: Int): Boolean {
        return nums[a].toLong() + nums[b] + nums[b + 1] + nums[b + 2] > target
    }
}

fun main() {
    println(
        Solution18().fourSum(
            arrayOf(
                0,0,0,-1000000000,-1000000000,-1000000000,-1000000000
            ).toIntArray(),
            -1000000000
        )
    )
}